package cn.csq;

import java.util.ArrayList;
import java.util.LinkedList;

public class DataStructureMainTest {

}


class ArrayListTest{
    public static void main(String[] args) {
        ArrayList<String> strings = new ArrayList<>();
        strings.add("1");
        strings.add("2");

        String s = strings.get(0);
        System.out.println("s = " + s);
        strings.remove(0);
        System.out.println("s = " + strings.get(0));
        // 数组最重要的是连续的内存空间，数据+索引。
        // 如果当前索引的值被remove移动后面的数组会补充上
        // arrayList 数组：内存连续的空间，访问按索引来访问，速度很快 访问是o(1),插入删除o(n)
        // 数组插入和删除元素的，所有元素都会进行变动，来保障数组连续性和索引的正确性；插入新元素，旧元素需要挪动；删除旧元素，进行挪动。


        // 不同于hashMap 散列数据结构，索引是标记算法

        LinkedList<String> stringLinkedList = new LinkedList<>();
        stringLinkedList.add("1");
        stringLinkedList.peek(); // 查看顶部元素
        stringLinkedList.poll(); // 移除并返回集合顶部元素
        stringLinkedList.pop(); //  removeFirst； addFirst(); removeLast(); addLast()

        // linkedList链表，内存空间不用连续，每个node节点记录了数据+指针，记录了上下节点的指针。
        // 插入和删除很快，只需要找到对应的位置，o(1) 。 访问o(N) 需要从头或者尾巴去遍历找到对应的值


        // 红黑树 平衡二叉树
        // B 多路平衡树，非叶子节点存储了数据，空间太大
        // B+ 多路平衡树，非叶子节点只存储索引

    }
}
